/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;  // 当前节点指针
        int n = 0;  // 计算链表长度
        while(cur != nullptr)  // 遍历链表计算长度
        {
            ++n;
            cur = cur->next;
        }
        n /= k;  // 计算需要翻转的组数

        cur = head;  // 重置当前节点为头节点
        ListNode* newHead = new(ListNode);  // 创建虚拟头节点
        ListNode* prev = newHead;  // 前驱节点初始化为虚拟头
        while(n--)  // 处理每组翻转
        {
            ListNode* tmp = cur;  // 保存当前组的第一个节点，翻转后将成为该组的最后一个节点
            int cntK = k;  // 计数器，处理k个节点
            while(cntK--)  // 组内翻转
            {
                ListNode* prevNext = cur->next;  // 保存当前节点的下一个节点
                cur->next = prev->next;  // 将当前节点插入到前驱节点之后
                prev->next = cur;  // 更新前驱节点的next
                cur = prevNext;  // 移动到下一个待处理节点
            }
            prev = tmp;  // 更新前驱节点为当前组的最后一个节点
        }
        prev->next = cur; // 连接剩余不需要翻转的节点
        cur = newHead->next;  // 获取真正的头节点
        delete newHead;  // 释放虚拟头节点
        return cur;  // 返回翻转后的链表头
    }
};